package Sort;

public class InsertionSort {
    public static void sort(int[] a ){
        for(int low=1; low<a.length; low++){
            int t=a[low];
            int i=low-1;
            //自右向左找比插入元素小的元素,找到后退出循环,那么i+1就是要插入的位置
            while(i>=0 && a[i]>t){
                a[i+1]=a[i];
            }
            if(i!=low-1){
                a[i+1]=t;
            }
        }

    }
}
